#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
#include "token.h"

using namespace std;

double evalExp(string expr);

int main(void)
{
	string expression;
	double ans;
	cout << "Input the expression which is begin and end with '#': ";
	cin >> expression;
	ans = evalExp(expression);										//计算表达式的值
	cout << "The answer is " << ans << endl;
	return 0;
}

//从表达式字符串中提取算符序列
void getToken(string expr, vector<Token *> &tArr)
{
	unsigned int index = 0;
	string op("+-*/()#"), numStr;
	while(index < expr.length())
	{
		if((int)op.find(expr[index]) == -1)							//若不是操作符
		{
			numStr = "";
			do
			{
				numStr += expr[index];
				index++;
			}while((int)op.find(expr[index]) == -1);				//将这个数保存在字符串中
			Num *num = new Num;
			num->value = atof(numStr.c_str());
			tArr.push_back(num);									//将字符串转化为数并存入算符序列
		}
		else
		{
			Oper *oper = new Oper;
			oper->oper = expr[index];
			tArr.push_back(oper);									//将操作符存入算符序列
			index++;
		}
	}
	return;
}

//判断运算符优先级，优先级'*'表示该种情况不会出现，即表达式非法
char Precede(char left, char right)
{
	string ops("+-*/()#");
	int nleft, nright;
	char pri[7][7] = {
		{'>','>','<','<','<','>','>'},
		{'>','>','<','<','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'<','<','<','<','<','=','*'},
		{'>','>','>','>','*','>','>'},
		{'<','<','<','<','<','*','='},
	};
	nleft = ops.find(left);
	nright = ops.find(right);
	return pri[nleft][nright];
}

//表达式求值主程序
double evalExp(string expr)
{
	vector<Token *> tArr;
	vector<Token *>::iterator p_token;
	vector<char> stack_op; 
	vector<char>::iterator p_op;
	vector<double> stack_num;
	vector<double>::iterator p_num;
	string oparr("+-*/()#.");
	int index_b, index_e, count=1;
	unsigned int index;
	char op;
	double numa, numb, ans;

	//将表达式部分(两个井号中间的部分)取出
	index_b = expr.find('#');
	index_e = expr.find('#', index_b+1);
	if(index_b == -1 || index_e == -1)
	{
		cout << "The form of the expression is not correct!" << endl;
		cout << "The expression must be in the between of two pound signs!" << endl;
		return 0;
	}
	expr = expr.substr(index_b, index_e-index_b+1);

	//判断表达式是否含有非法字符
	for(index=0; index < expr.length(); index++)
		if(((int)oparr.find(expr[index]) == -1) && !(expr[index] >= '0' && expr[index] <= '9'))
		{
			cout << "The expression has illegal character!" << endl;
			return 0;
		}

	getToken(expr, tArr);											//将每一个操作符和操作数提取出来
	cout << "The expression is: ";
	for(p_token = tArr.begin(); p_token != tArr.end(); p_token++)	//输出表达式序列
	{
		(*p_token)->print();
	}
	cout << endl;

	p_token = tArr.begin();
	stack_op.push_back(((Oper *)*p_token)->oper);
	p_token++;
	cout << "------------------------------------------------------------" << endl;
	cout << "Step\tOPTR\tOPND(s)\tChar/Num\tOperation" << endl;
	cout << "------------------------------------------------------------" << endl;
	while(p_token != (tArr.end()-1) || stack_op.back()!='#')
	{
		cout << count << "\t";
		for(p_op = stack_op.begin(); p_op != stack_op.end(); p_op++)
			cout << *p_op;
		cout << "\t" << stack_num.size() << "\t";
		(*p_token)->print();
		cout << "\t\t";

		if((*p_token)->isOper())									//若算符为运算符
		{
			op = ((Oper *)*p_token)->oper;
			switch(Precede(stack_op.back(), op))					//判断该运算符与栈顶运算符的优先程度
			{
				case '<':											//若栈顶运算符优先权低，则将当前运算符压栈
					stack_op.push_back(op);
					p_token++;
					cout << "Push(OPTR): " << op;
					break;
				case '=':											//若栈顶运算符优先权与当前运算符相等，则表示脱去括号
					stack_op.pop_back();
					p_token++;
					cout << "Pop(OPTR): " << op;
					break;
				case '>':											//若栈顶运算符优先权高，则将数字栈的最顶两数字弹出并运算，所得运算结果压回栈中
					op = (stack_op.back());
					stack_op.pop_back();
					numb = stack_num.back();
					stack_num.pop_back();
					if(stack_num.empty())							//判断是否有两个运算符连续出现的情况（如3+-5）					
					{
						cout << endl << "The expression is invalid!" << endl;
						return 0;
					}
					numa = stack_num.back();
					stack_num.pop_back();
					cout << "Calc: " << numa << op << numb;
					switch(op)
					{
						case '+': ans = numa+numb; break;
						case '-': ans = numa-numb; break;
						case '*': ans = numa*numb; break;
						case '/': ans = numa/numb; break;
					}
					stack_num.push_back(ans);
					break;
				default:											//优先级判断错误，表达式非法
					cout << endl << "The expression is invalid!" << endl;
					return 0;
			}
		}
		else														//若算符不是运算符，则压进数字栈
		{
			cout << "Push(OPND): " << ((Num *)*p_token)->value;
			stack_num.push_back(((Num *)*p_token)->value);
			p_token++;
		}
		cout << endl;
		count++;
	}

	cout << count << "\t";
	for(p_op = stack_op.begin(); p_op != stack_op.end(); p_op++)
		cout << *p_op;
	cout << "\t" << stack_num.size() << "\t";
	(*p_token)->print();
	cout << "\t\t" << "Return(Gettop(OPND))" << endl;
	cout << "------------------------------------------------------------" << endl;

	return stack_num.back();
}
//#(123.456*789.3)+135.2*(7+9)#